package ljl.codetop300;

import java.util.ArrayList;
import java.util.List;

/**
 * 当场放弃！我可是个聪明人
 */
public class _442_find_duplicate {

  /**
   * 这个数组很特殊，有的有一个，有的有两个
   * 说明有的数字没有
   * 把数字归位，只有一个的肯定可以归位，有两个的没法整，只能一个归位，剩的那一个肯定位置是错的
   * 最后位置不对的
   */
  static class off1 {
    public List<Integer> findDuplicates(int[] nums) {
      int n = nums.length;
      for (int i = 0; i < n; ++i) {
        // 不停的把 i 这个位置的数字搞走，直到：
        while (nums[i] != nums[nums[i] - 1]) {
          swap(nums, i, nums[i] - 1);
        }
      }
      List<Integer> ans = new ArrayList<>();
      for (int i = 0; i < n; ++i) {
        if (nums[i] - 1 != i) {
          ans.add(nums[i]);
        }
      }
      return ans;
    }

    public void swap(int[] nums, int index1, int index2) {
      int temp = nums[index1];
      nums[index1] = nums[index2];
      nums[index2] = temp;
    }
  }

  static class copyoff1 {
    public List<Integer> findDuplicates(int[] nums) {
      for (int i = 0; i < nums.length; i++) {
        while (nums[i] != nums[nums[i] - 1]) {
          swap(nums, i, nums[i] - 1);
        }
      }
      List<Integer> res = new ArrayList<>();
      for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
          res.add(nums[i]);
        }
      }
      return res;
    }
    void swap(int[] nums, int i, int j) {
      int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }
  }

  /**
   * 阴间解法
   * 第一次遇到数字 x，把 x 那个位置的数字搞成负数，说明 x 遇到过了
   * 如果第二次遇到负数 x 了，说明遇到了两次，放进去
   */
  static class off2 {
    public List<Integer> findDuplicates(int[] nums) {
      int n = nums.length;
      List<Integer> ans = new ArrayList<>();
      for (int i = 0; i < n; ++i) {
        int x = Math.abs(nums[i]);
        if (nums[x - 1] > 0) {
          nums[x - 1] = -nums[x - 1];
        } else {
          ans.add(x);
        }
      }
      return ans;
    }
  }

  static class copyoff2 {
    public List<Integer> findDuplicates(int[] nums) {
      List<Integer> res = new ArrayList<>();
      for (int i = 0; i < nums.length; i++) {
        int x = Math.abs(nums[i]);
        if (nums[x - 1] > 0) {
          nums[x - 1] = -nums[x - 1];
        } else {
          res.add(x);
        }
      }
      return res;
    }
  }
}
